超酷算法（2）：分组密码与安全排列
（点击上方公众号，可快速关注）
英文：blog.notdot.net
译者：伯乐在线 - 威士忌
链接：http://blog.jobbole.com/83218/
作为开始，我假设你知道什么是排列，简单说就是按特定的顺序对序列进行洗牌。比如，值域1-10的排列为{5,2,1,6,8,4,3,9,7,10} 。一个安全的排列是攻击者即使有该排列的任意子集，都无法确定其它任何一个元素的顺序。这里有个简单的例子是使用一个安全加密的伪随机数生成器，用一个密钥作为种子，并用它来打乱你的序列。
如果你想生成一个非常非常大的排列，一个如此大的预计算和存储是不是不太现实？此外，你是否希望它是个安全序列？这里有个非常巧妙的方法，我们可以使用分组密码，使我们能够产生超过数值范围内的任何一个安全排列，而不必对它们进行预计算。
分组密码，没人不熟悉，它是密码学中一种常见的基础元素。它是由多块一定长度的密文组成，密文一般为64或128位的加密串。相同的密钥和相同的明文，它只可能生成相同的密文。超过一个块大小的信息使用一系列操作模式中的某一种方式加密，继而可以针对比单个块大许多的消息进行安全的加密和解密。使用分组密码加密，选择操作模式是至关重要的。为了能生成一个安全排列，无论如何，我们只打算每次加密单个块，所以我们不必担心操作模式。
如果你知道分组密码是如何运作的，你肯定能获得一个安全的排列。将给定长度的任意块（考虑下块的数量非常大的情况）用唯一的方式转换为另外一个块，且能将它再次转换回来。如果我们逐步加密更大的数字（1,2,3等等），我们保证能得到看上去随机的序列，只要不重复输入。这点很容易证明：假如它是重复的，那你会有两个输入数字被解码为同一个输出数字，这样就不可能有独一无二的解码。分组密码所持有的这些特性也正是对我们有用的特性。
你说，一切都挺好，但如果我想要一个不是2的幂次值域内的排列该如何？这里有个聪明的小技巧，就是取一个块长度略大于你想要的长度的分组密码，使用上面描述的方法，逐步加密序列中的更大数值，以产生排列中的元素。当加密后的值超出你想要的排列值域之外，只需再次加密。重复这样的方式直到你给到你想要的值域内的数值。同样，我们能保证分组密码的唯一性，并且我们也能保证（穷举方式）最终获得了一个理想值域内的数值。
很显然，在追寻这条路之前我们需要考虑一些因素。你要选择一个分组密码，是不是比你想生成的序列的值域要大，最好是2的幂次。密码值域和排列值域的比率确定了你运行的平均时间， 因此，如果密码是你排列的值域的四倍时，你就对每个值平均需要四次加密。这可能产生问题，因为大多数密码是64，128或者更多位。为了这个目的，我们找到适应性比较强的TEA加密算法，它很容易构造32,64,128或者更长位的变体，并且位操作在main主循环那很容易调整，也可产生4的幂次长度的密码，而无需将密码缩短至容易被暴力破解的长度。
另外值得一提的是，虽然这个技术的目的是生成非常大的安全排列，但对那些并不注重安全的排列同样有用 – 你的密钥可作为生成排列的随机种子。在许多情况下这种方法同样有帮助，基本上它是个映射函数可以用来索引排列的数值，这样你可以计算出该排列的任意子集的值。
最后，请记住，由于可能的排列数呈阶乘级增长，你的密钥空间肯定大大小于排列的数量。这个对于大多数应用可能并不重要，因为如此庞大的排列不可能一个个枚举过去。但是，如果你的密钥过短，它就有可能被攻击者利用枚举密钥的方式来找出可能生成的排列。
更新：Yossi Oren在评论里留了分优秀的论文连接。它涵盖了我的描述（当然更全面）。
译者简介